The present invention relates to data networking and more particularly to systems and methods for rerouting around failed links and/or nodes.
The Internet and IP networks in general have become enablers for a broad range of business, government, and personal activities. More and more, the Internet is being relied upon as a general information appliance, business communication tool, entertainment source, and as a substitute for traditional telephone networks and broadcast media. As the Internet expands its role, users become more and more dependent on uninterrupted access.
To assure rapid recovery in the event of failure of a network link or node, so-called “Fast Reroute” techniques have been developed. In a network employing Fast Reroute, traffic flowing through a failed link or node is rerouted through one or more preconfigured backup tunnels. The preconfigured backup tunnels facilitate a key goal of Fast Reroute techniques, the redirection of interrupted traffic within tens of milliseconds. This minimizes impact on the user experience.
The Fast Reroute techniques have been developed in the context of MPLS (Multiprotocol Label Switching) where traffic flows through label switched paths (LSPs). When an element such as a link or node fails, all of the LSPs using that failed element are redirected through preconfigured backup tunnels that route around the impacted segments of the LSPs. These backup tunnels are generally used only for a very short time since simultaneously with the rerouting through the backup tunnels, the head ends of all the affected primary LSPs are notified of the failure. This causes the head ends to reroute the primary LSPs around the failures so that the backup tunnels are no longer needed.
A key aspect of meeting the reliability and quality of service objectives of Fast Reroute is the switchover time from the failed segments of the protected primary LSPs to their preconfigured backup tunnels. A certain amount of time transpires while the failure is detected and the actual switchover occurs. In a modern high-speed packet forwarding device, the disposition of a received packet is determined by the contents of a compact forwarding table stored in high speed memory. The forwarding table's entries include so-called “adjacency” information that is used to encapsulate the packet for its transit to the next-hop node in addition to one or more labels that are imposed on the packet to implement the MPLS scheme. Each forwarding equivalence class forwarding over a primary LSP will have an entry in such a table. For optimal performance, only a single look-up is required to access the contents of this table and this look-up is based on the forwarding equivalence class (incoming label or longest match destination address prefix). When an LSP's traffic is to be rerouted into a backup tunnel, the switchover is accomplished by rewriting all of the appropriate entries.
A problem arises, however, in that a single failed link or node may carry a large number of protected LSPs and therefore a large number of entries corresponding to the forwarding equivalence classes forwarding over those protected LSPs. A switchover may therefore require rewriting a large number of entries. If, for example, one thousand entries must be rewritten in response to the failure of a single link and each entry rewrite requires 150 microseconds, the switchover process will consume 150 milliseconds during which service will be interrupted. This level of delay is unacceptable.
What is needed are readily scaleable systems and methods for accelerating the switchover to preconfigured backup tunnels upon failure of a protected link or node, while at the same time not slowing down the normal forwarding process.